#!/usr/bin/env python
# -*- coding: utf-8 -*-
# @Time    : 2020/6/11 15:10
# @USER    : Shengji He
# @File    : SudokuSolver.py
# @Software: PyCharm
# @Version  : Python-
# @TASK:
from typing import List


class Solution:
    def __init__(self):
        self.zero_record = {0: []}
        self.level = 0

    def is_valid(self, board):
        boxes = {i: {str(j): 0 for j in range(1, 10)} for i in range(9)}
        rows = {i: {str(j): 0 for j in range(1, 10)} for i in range(9)}
        columns = {i: {str(j): 0 for j in range(1, 10)} for i in range(9)}
        blacks = {}
        for i in range(9):
            for j in range(9):
                if board[i][j] == '.':
                    blacks[(i, j)] = []
                elif board[i][j] == '0':
                    return False, blacks
                else:
                    rows[i][board[i][j]] += 1
                    columns[j][board[i][j]] += 1
                    boxes[i // 3 * 3 + j // 3][board[i][j]] += 1
                    if rows[i][board[i][j]] > 1 or columns[j][board[i][j]] > 1 or \
                            boxes[i // 3 * 3 + j // 3][board[i][j]] > 1:
                        return False, blacks
        for idx in blacks:
            for ele in range(1, 10):
                if rows[idx[0]][str(ele)] == 0 and columns[idx[1]][str(ele)] == 0 and \
                        boxes[idx[0] // 3 * 3 + idx[1] // 3][str(ele)] == 0:
                    blacks[idx].append(str(ele))

        return True, blacks

    def solveSudoku(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.

        Write a program to solve a Sudoku puzzle by filling the empty cells.

        A sudoku solution must satisfy all of the following rules:
            - Each of the digits 1-9 must occur exactly once in each row.

            - Each of the digits 1-9 must occur exactly once in each column.

            - Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-boxes of the grid.

            - Empty cells are indicated by the character '.'.

        Note:
            - The given board contain only digits 1-9 and the character '.'.

            - You may assume that the given Sudoku puzzle will have a single unique solution.

            - The given board size is always 9x9.

        :param board: List[List[str]]
        """
        flag, blacks = self.is_valid(board)
        while flag:
            if not blacks:
                self.level -= 1
                return
            blacks = sorted(blacks.items(), key=lambda x: len(x[1]))
            for key, values in blacks:
                if len(values) == 1:
                    board[key[0]][key[1]] = values[0]
                    self.zero_record[self.level].append(key)
                else:
                    if not self.zero_record[self.level]:
                        for ele in values:
                            board[key[0]][key[1]] = ele
                            level = self.level
                            self.level += 1
                            self.zero_record[self.level] = []
                            self.solveSudoku(board)
                            flagt, _ = self.is_valid(board)

                            if not flagt:
                                for i in range(level + 1, self.level + 1):
                                    if not self.zero_record[i]:
                                        pass
                                    else:
                                        for idx in self.zero_record[i]:
                                            board[idx[0]][idx[1]] = '.'
                                        self.zero_record[i] = []
                                self.level = level
                                board[key[0]][key[1]] = '.'
                            else:
                                self.zero_record[self.level].append(key)
                                return
                        if not self.zero_record[self.level]:
                            board[key[0]][key[1]] = '0'
                            self.zero_record[self.level].append(key)
                            return
                    else:
                        self.level += 1
                        self.zero_record[self.level] = []
                        break
            flag, blacks = self.is_valid(board)
        if not flag:
            self.level -= 1
        return


if __name__ == '__main__':
    S = Solution()
    board = [
        [".", "3", ".", ".", "7", ".", ".", ".", "."],
        ["6", ".", ".", "1", ".", "5", ".", ".", "."],
        [".", "9", "8", ".", ".", ".", ".", "6", "."],
        ["8", ".", ".", ".", "6", ".", ".", ".", "3"],
        ["4", ".", ".", "8", ".", "3", ".", ".", "1"],
        ["7", ".", ".", ".", "2", ".", ".", ".", "6"],
        [".", "6", ".", ".", ".", ".", "2", "8", "."],
        [".", ".", ".", "4", "1", "9", ".", ".", "5"],
        [".", ".", ".", ".", "8", ".", ".", "7", "."]
    ]
    S.solveSudoku(board)
    print('done')
